#include<numeric>
#include<vector>
using namespace std;
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2)return false;
        int n=nums.size(),m=sum/2;
        nums.insert(nums.begin(),0);
        vector<vector<bool>>dp(n+1,vector<bool>(m+1,false));
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=(dp[i-1][j]||(j>=nums[i]&&dp[i-1][j-nums[i]]));
            }
        }
        return dp[n][m];
    }
};
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2)return false;
        int n=nums.size(),m=sum/2;
        vector<bool>dp(m+1,false);
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=m;j>=nums[i-1];j--){
                dp[j]=(dp[j]||dp[j-nums[i-1]]);
            }
        }
        return dp[m];
    }
};